#include <iostream>
#include <vector>    // 竞赛最常用的动态数组
#include <array>     // 固定大小数组
#include <algorithm> // 算法库
using namespace std;

// 静态数组
int staticArray[5] = {1, 2, 3, 4, 5};

// 数组基本操作示例
void arrayDemo() {
    cout << "=== 数组基本操作演示 ===" << endl;
    
    // 访问元素
    cout << "第一个元素: " << staticArray[0] << endl;
    
    // 修改元素
    staticArray[0] = 10;
    cout << "修改后第一个元素: " << staticArray[0] << endl;
    
    // 遍历数组
    cout << "数组内容: ";
    for(int i = 0; i < 5; i++) {
        cout << staticArray[i] << " ";
    }
    cout << endl;
}

// 动态数组示例
void dynamicArrayDemo() {
    cout << "\n=== 动态数组演示 ===" << endl;
    
    // 创建动态数组
    int size = 5;
    int* dynamicArray = new int[size];
    
    // 初始化数组
    for(int i = 0; i < size; i++) {
        dynamicArray[i] = (i + 1) * 10;
    }
    
    // 显示数组内容
    cout << "动态数组内容: ";
    for(int i = 0; i < size; i++) {
        cout << dynamicArray[i] << " ";
    }
    cout << endl;
    
    // 释放内存
    delete[] dynamicArray;
    cout << "动态数组已释放" << endl;
}

// 二维数组示例
void twoDimensionalArray() {
    cout << "\n=== 二维数组演示 ===" << endl;
    
    int matrix[3][3] = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    
    cout << "3x3矩阵:" << endl;
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
}

// 数组搜索示例
void arraySearchDemo() {
    cout << "\n=== 数组搜索演示 ===" << endl;
    
    int arr[] = {10, 25, 30, 45, 50, 60, 75, 80};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 45;
    
    cout << "在数组 {10, 25, 30, 45, 50, 60, 75, 80} 中搜索 " << target << endl;
    
    // 线性搜索
    for(int i = 0; i < n; i++) {
        if(arr[i] == target) {
            cout << "找到元素 " << target << " 在索引 " << i << " 处" << endl;
            return;
        }
    }
    cout << "未找到元素 " << target << endl;
}

// 数组插入示例
void arrayInsertDemo() {
    cout << "\n=== 数组插入演示 ===" << endl;
    
    int arr[10] = {1, 2, 4, 5, 6}; // 假设数组有5个元素，容量为10
    int n = 5; // 当前元素个数
    int pos = 2; // 插入位置
    int value = 3; // 要插入的值
    
    cout << "插入前数组: ";
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    
    // 从后往前移动元素
    for(int i = n; i > pos; i--) {
        arr[i] = arr[i-1];
    }
    
    // 插入新元素
    arr[pos] = value;
    n++;
    
    cout << "在位置 " << pos << " 插入 " << value << " 后: ";
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// ================ 竞赛常用写法 ================

// 竞赛推荐：使用vector
void vectorContestDemo() {
    cout << "\n=== 竞赛常用：vector演示 ===" << endl;
    
    // 1. 创建和初始化
    vector<int> arr = {1, 2, 3, 4, 5};  // 初始化列表
    vector<int> arr2(5, 0);              // 5个0
    vector<int> arr3(10);                // 10个默认值
    
    // 2. 常用操作
    arr.push_back(6);                    // 尾部插入 O(1)
    arr.pop_back();                      // 尾部删除 O(1)
    arr.insert(arr.begin() + 2, 10);     // 中间插入 O(n)
    arr.erase(arr.begin() + 1);          // 删除元素 O(n)
    
    // 3. 访问和遍历
    cout << "vector大小: " << arr.size() << endl;
    cout << "是否为空: " << arr.empty() << endl;
    cout << "第一个元素: " << arr[0] << endl;
    cout << "最后一个元素: " << arr.back() << endl;
    
    // 4. 竞赛常用遍历方式
    cout << "遍历方式1 (索引): ";
    for(int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    
    cout << "遍历方式2 (范围for): ";
    for(int x : arr) {
        cout << x << " ";
    }
    cout << endl;
    
    // 5. 二维vector（竞赛常用）
    int n = 3, m = 4;
    vector<vector<int>> matrix(n, vector<int>(m, 0)); // n×m矩阵
    
    cout << "二维vector矩阵:" << endl;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            matrix[i][j] = i * m + j + 1;
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
    
    // 6. 竞赛常用技巧
    vector<int> nums = {5, 2, 8, 1, 9};
    sort(nums.begin(), nums.end());      // 排序
    reverse(nums.begin(), nums.end());   // 反转
    
    cout << "排序后反转: ";
    for(int x : nums) cout << x << " ";
    cout << endl;
    
    // 7. 查找操作
    auto it = find(nums.begin(), nums.end(), 5);
    if(it != nums.end()) {
        cout << "找到5，位置: " << (it - nums.begin()) << endl;
    }
}

// 竞赛常用：array（固定大小）
void arrayContestDemo() {
    cout << "\n=== 竞赛常用：array演示 ===" << endl;
    
    array<int, 5> arr = {1, 2, 3, 4, 5};
    
    // 常用操作
    cout << "array大小: " << arr.size() << endl;
    cout << "第一个元素: " << arr[0] << endl;
    cout << "最后一个元素: " << arr.back() << endl;
    
    // 排序（竞赛常用）
    sort(arr.begin(), arr.end());
    cout << "排序后: ";
    for(int x : arr) cout << x << " ";
    cout << endl;
}

// 竞赛常用：数组代替map的技巧
void arrayAsMapDemo() {
    cout << "\n=== 竞赛技巧：数组代替map ===" << endl;
    
    // 当键范围较小时，用数组代替map更高效
    vector<int> cnt(1000001, 0);  // 计数数组
    
    vector<int> nums = {1, 2, 2, 3, 3, 3, 4};
    for(int x : nums) {
        cnt[x]++;  // 计数
    }
    
    cout << "数字频率统计:" << endl;
    for(int i = 1; i <= 4; i++) {
        cout << i << ": " << cnt[i] << " 次" << endl;
    }
}

int main() {
    // 传统数组演示
    arrayDemo();
    dynamicArrayDemo();
    twoDimensionalArray();
    arraySearchDemo();
    arrayInsertDemo();
    
    // 竞赛常用写法
    vectorContestDemo();
    arrayContestDemo();
    arrayAsMapDemo();
    
    cout << "\n=== 竞赛选择指南 ===" << endl;
    cout << "1. 动态数组：使用 vector<T>" << endl;
    cout << "2. 固定数组：使用 array<T, N>" << endl;
    cout << "3. 二维数组：使用 vector<vector<T>>" << endl;
    cout << "4. 计数：当范围小时用数组代替map" << endl;
    
    cout << "\n=== 时间复杂度总结 ===" << endl;
    cout << "访问: O(1)" << endl;
    cout << "插入/删除: O(n)" << endl;
    cout << "搜索: O(n)" << endl;
    
    return 0;
}
